#!/usr/bin/python

import time, sys
from math import ceil, sqrt, floor


""" 

A Hamming number is a positive number which has no prime factor larger than 5.
So the first few Hamming numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15.
There are 1105 Hamming numbers not exceeding 10^8.

We will call a positive number a generalised Hamming number of type n, if it has no prime factor larger than n.
Hence the Hamming numbers are the generalised Hamming numbers of type 5.

How many generalised Hamming numbers of type 100 are there which don't exceed 10^9?
    
"""

def isprime(num):
    ans = True
    if num <= 1:
        return False
    if num % 2 == 0:
        return False
    for n in xrange(3, int(ceil(sqrt(num)))+1):
        if num % n == 0:
            return False
    return
    
def ishamming(n, type, primes):  
    if n < 1:
        return False
    if n <= type:
        return True
    if isprime(n):
        return False
    # check odd factors up to the sqrt to see if they are prime and over type
    for prime in primes:
        if n % prime == 0 and prime > type:
            return False
    
    # for i in ??
        # n / i

    
    return True
    
def main():
    start = time.time()
    
    # testing code
    hammingtrue = [ 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15 ]
    # hammingfalse = [ num for num in xrange(1, 16) if num not in hammingtrue  ]
    type = 5
    limit = 15
    
    primes = [ i for i in xrange( 3, int(limit/2)+1, 2) if isprime(i) ]
    print 'primes returned'  
    print primes
    print len(primes)    
        
    for n in xrange(1, int(limit) + 1 ):
        if isprime(n) and n > type:
            result = True
        result = ishamming(n, type, primes)
        print 'result for {0}: {1}'.format(n, result),
        if result is True:
            if n in hammingtrue:
                print 'OK'
            else:
                print 'FAIL'
        if result is False:
            if n not in hammingtrue:
                 print 'OK'
            else:
                print 'FAIL'           
        
    hammingtrue = []
    limit = 1e8
    type = 5
    
    primes = [ i for i in xrange(int(limit/2)+1) if isprime(i) ]
    
    print 'primes returned'  
    print len(primes)    
    
    # n is the number to be detmined ?hamming
    for n in xrange(3, int(limit) + 1, 2 ):
        if ishamming(n, type, primes):
            hammingtrue.append(n)
    
    print 'there are {0} hamming codes of type {1} not exceeding {2}'.format(len(hammingtrue), type, limit)
    
    
    # hammingtrue = []
    # limit = 1e9
    # type = 100
    # for n in xrange(1, int(ceil(sqrt(limit))) + 1 ):
        # if ishamming(n, type, primes) is True:
            # hammingtrue.append(n)
    # print 'there are {0} hamming codes of type {1} not exceeding {2}'.format(len(hammingtrue), type, limit)
    
    print '{0:.2f} s'.format(time.time() - start)  

# solution: 
    
if __name__ == '__main__':
    main()

